Ever since the development of the first camera it seems that individuals have been interested in capturing an image for display on some sort of image media. One example is the demand for home and commercial videos. The emergence of personal computers (PCS) and computer networks has accelerated this interest. It is now possible for a video camera to capture images, transfer the images through a network, store the images on a PC, and play back the captured images on a PC monitor anywhere in the world. The capability to transfer and store image data on a PC is given, in part, by the use of compression technologies to reduce the large amount of digital data needed to reproduce an image with high levels of quality. One such compression technology was introduced by Sony Corporation titled "Specifications of Consumer-use Digital VCRs using 6.3 mm magnetic tape," December 1994, HD Digital VCR conference ("DV standard").
Conventional PCS, however, cannot adequately play back full motion videos compressed (sometimes referred to as "encoded") using the DV standard. The problem stems from the decoding algorithms used to decode the DV encoded video signals. For example, conventional DV decoding techniques implemented using a Pentium II microprocessor by Intel Corporation operating at 300 megahertz (MHZ) are only capable of playing back a DV encode video at 2-4 frames per second using a full size video window (e.g., 720.times.480 pixel resolution). Play back at 2-4 frames per second is far below industry standard for video quality, which is currently at 30 frames per second.
More particularly, conventional DV decoding algorithms have difficulty decoding the variable length codes generated by the DV encoding process. During the encoding process, video signals are compressed using two techniques referred to as run length encoding and variable length encoding.
Run length encoding takes a block of quantized coefficients and converts it to a series of "run" values and "amp" values. The block of quantized coefficients is really a matrix of zero and non-zero values. Run length encoding reduces the number of zeros by representing a series of zeros by a single number (ie., run value) followed by the non-zero value (ie., amp value). Each run and amp value represents a single code-pair, often referred to as a "run amp code" (RAC).
Variable length encoding converts each RAC into a VLC. One example of a variable length encoding technique is referred to as "Huffman encoding." Huffman encoding is a minimum length code. This means that given the statistical distribution of gray levels, Huffman encoding will generate a code word that is as close as possible to the minimum bound (the entropy). The resulting code words are of unequal length, hence the term VLC.
The result of the encoding process is a stream of bits having a zero value or a one value ("bitstream"). During the decoding process, the play back system receives the bitstream, determines the number of bits comprising each VLC, and transforms the VLC back into its corresponding RAC ("VLC decoding"). Conventional DV decoders, however, cannot accomplish VLC decoding fast enough to provide high quality play back of the decoded video signals.
For example, some conventional DV decoders use a simple translation table to perform VLC decoding. These systems read the encoded bit stream into a buffer one bit at a time and test the buffer after reading each bit to determine whether the buffer contains a complete code that can be decoded or whether another bit needs to be read. Once the buffer contains a complete VLC, the decoder looks up the VLC in a lookup table and retrieves a matching RAC. Such a method, however, requires a large number of processing cycles and a large memory to store the relatively large translation table.
Another method for VLC decoding is described in U.S. Pat. No. 5,646,618 (the "Walsh patent"). The VLC decoder reads K bits at a time into a buffer. The K bits are used as an index into a lookup table to retrieve a table entry from the lookup table. The lookup table has a table entry for each possible K-bit value. Each table entry indicates whether there are any complete VLCs at the start of the K bits and, if so, the table entry also indicates the decoded values for one, two or three VLCs. The table entry also indicates the total number of bits used to encoded the one, two or three VLCs. If the VLC is longer than K bits, additional J bits are retrieved from the bit stream and are used as an index into a second table having a table entry for each possible K+J bit value.
The technique described in the Walsh patent, however, suffers from the same problems as the bit-by-bit buffering technique described previously. The lookup tables described in the Walsh patent require a relatively large amount of memory i.e., 8 kilobytes). This increases hardware costs for the decoder. Moreover, the search algorithm for these lookup tables is fairly complex and therefore expensive in terms of processing cycles.
In view of the foregoing, it can be appreciated that a substantial need exists for a method and apparatus for VLC decoding that solves the above-mentioned problems.